package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC145 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {


        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            postOrderTraversalIterate(root, res);
            return res;
        }

        public void postOrderTraversalRecur(TreeNode root, List<Integer> res) {
            if (null == root) return;
            postOrderTraversalRecur(root.left, res);
            postOrderTraversalRecur(root.right, res);
            res.add(root.val);
        }

        public void postOrderTraversalIterate(TreeNode root, List<Integer> res) {
            if (null == root) return;
            TreeNode cur = root, pre = null;
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null) {
                goLeftSide(cur, stack);
                if (!stack.isEmpty()) {
                    cur = stack.pop();
//                    有如下两种情况：
//                    1、当前经过节点是叶子节点。
//                    2、当前经过节点的右子节点是上一次访问的节点。
                    if (cur.right == null || cur.right == pre) {
                        res.add(cur.val);
                        pre = cur;
                        cur = null;// 此处为了跳过下一次循环的访问左子节点的过程，
                        // 直接进入栈的弹出阶段，因为但凡在栈中的节点，它们的左子节点都肯定被经过且已放入栈中。
                    } else {
                        //不访问节点
                        stack.push(cur);
                        cur = cur.right;
                    }
                }
            }
        }

        public void goLeftSide(TreeNode cur, Stack<TreeNode> stack) {
            while (null != cur) {
                stack.push(cur);
                cur = cur.left;
            }
        }

    }

    public void run() {
        Solution solution = new Solution();
        TreeNode root = TreeNode.createTree("1,2,3,4,5");
        System.out.println(solution.postorderTraversal(root));
    }

    public static void main(String[] args) throws Exception {
        LC145 an = new LC145();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
